package q32_longestValidParentheses;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public static void main(String[] args) {
        String s = "())()";
        int res = longestValidParentheses(s);
        System.out.println(res);
    }

    // 最长有效括号
    public static int longestValidParentheses(String s) {

        // 栈的方式
        Deque<Integer> stack = new LinkedList<>();
        // 存储每一次有效长度
        int max = 0;
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {


            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();

                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max,i - stack.peek());
                }
            }
        }
        return max;
    }
}
